#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
using namespace std;


class Solution1 {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1;
        for (auto str : words)
        {
            hash1[str]++;
        }
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++)
        {
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {

                string in = s.substr(right, len);
                //hash2[in]++;
                if (hash1.count(in) && ++hash2[in] <= hash1[in])
                {
                    count++;
                }
                if (right - left + 1 > len * m)
                {
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out]-- <= hash1[out])
                    {
                        count--;
                    }
                    //hash2[out]--;
                    left += len;
                }
                if (count == m)
                {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};

class Solution2 {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        for (auto ch : t)
        {
            hash1[ch]++;
        }
        int hash2[128] = { 0 };
        int n = s.size();
        int m = t.size();
        long len = n + 1, pos = 0;
        for (int left = 0, right = 0, count = 0; right < n; right++)
        {

            char in = s[right];
            hash2[in]++;
            if (hash2[in] <= hash1[in])
            {
                count++;
            }
            while (count == m)
            {
                char out = s[left];
                if (hash2[out] <= hash1[out])
                {
                    count--;
                }
                hash2[out]--;
                if (right - left + 1 < len)
                {
                    len = right - left + 1;
                    pos = left;
                }

                left++;
            }
        }
        if (len == n + 1)
        {
            return "";
        }
        return s.substr(pos, len);
    }
};

int main()
{

    return 0;
}